package leetcode

//https://leetcode.com/problems/zigzag-conversion


fun main(args: Array<String>) {
//    ZigZagConversion().sort.main(Array<String>(0, { i -> "" }))

    println(ZigZagConversion().convert("PAYPALISHIRING", 3))
}

class ZigZagConversion {

    val s = "\"obanbumdladpycygtrgutpdzlajzovccwcqaycfjeibclzkgsqanifmtfxsusuyqzoqxsyjwgkatllbfdesljggpdalxvjnwygvqegpmspgdcjignctxiaonazkxiyvigrbkzqwsfexiogodkjatlqioptlatjkzcllbbhthorpezfhjqkecapqsidubmecoqnsrulakerofyyrpivrkkheumyxzdzpvmhmjvpvbgkhfkyusvneiwjcijajmbzjqiwzfnuhtgoaqmukhjrpfauojwzyxyhnjfooslxorlokzlwjunaanuqzqpzqqifzoupifnwyankayhjsujukgklyckqsswtiskrzxpzackccrlxnwrxecifeuvynrrxlbqkbgkdkufpnsmaqdavhkanfxluperciinlqxoctvrindifjkaqvcgaaruryntivitnhjqcghktnvywfbocfuchoyammwwjerxoapqiwbblwbjdeygksktijuwxqsiwjhklwbtvcwgaaqfeqlqkykthgpgwkostwfhsgapkzw\"\n" +
            "317" //Pay pal is hiring

    fun main(args: Array<String>) {
        val rowNum = 36
        println(zigzagConvert(s, rowNum))
    }


    /**i
     * p     nums1     h     n
     * nums1  p  l  s  i  i  g
     * y     i     r
     *
     *
     *
     *
     */
    private fun zigzagConvert(s: String, numRows: Int): String {
        val nonsense = '$'
        var column = 0
        if (numRows == 1)
            return s
        else {
            val gapColumn = numRows - 2

            column = s.length / (numRows + gapColumn) * (1 + gapColumn)
            var rest = s.length % (numRows + gapColumn)
            column += Math.max(1, rest - numRows + 1)
        }


        //1   0    1       1       1
        //1   1    1   1   1   1   1
        //1   0    1       1
        //
        //
        val _2d = Array(numRows, { i ->
            Array(column, { i ->
                nonsense
            })
        })
        var index = 0
        var j = 0
        var i = 0

        while (index < s.length) {
            while (index < s.length && i < numRows) {
                _2d[i++][j] = s[index]
                index++
            }
            i--//back to  index = column -1
            while (index < s.length && i > 0) {
                _2d[--i][++j] = s[index]
                index++
            }
            i++
        }


        val stringBuilder = StringBuilder(s.length)
        //read out the string
        for (i in 0 until _2d.size) {
            for (j in 0 until _2d[i].size) {
                print(_2d[i][j] + "\t")
                if (_2d[i][j] != nonsense)
                    stringBuilder.append(_2d[i][j])
            }
            println()
        }

        return stringBuilder.toString()
    }


    //1   0    1       1       1
    //1   1    1   1   1   1   1
    //1   0    1       1
    fun convert(s: String, numRow: Int): String {
        if (s.isEmpty() || numRow < 2 || (s.length <= numRow)) return s
        val stringBuilder = StringBuilder()

        val periodInterval = 2 * numRow - 2  //最大周期间隔

        //计算最大列，节省列上的查找时间，而不是用s 的长度作为边界条件


        //当前行计算 间隔
        for (currRow in 0 until numRow) {

//            //✔
//            var downInterval = periodInterval - numRow
//
//            //^
//            var upInterval = numRow

            //一行最多多少个字母
            var period = periodInterval - currRow * 2
            //最后一行 周期归零
            if (currRow == numRow - 1) period = periodInterval
            var index = currRow
            stringBuilder.append(s[currRow])
            for (i in 0 until s.length) {
                //每行
                index += period
                if (index < s.length) {
                    stringBuilder.append(s[index])
                    if (currRow == numRow - 1) period = periodInterval
                    else {
                        period = periodInterval - period
                        if (period == 0) period = periodInterval
                    }
                }
            }

        }
        return stringBuilder.toString()
    }

    //1   0    1       1       1
    //1   1    1   1   1   1   1
    //1   0    1       1
    /**
     *计算每一行的间隔周期
     * 依次算每一行
     */
    fun convert2(s: String, numRow: Int): String {

        if (s.length < numRow || numRow <= 1) return s

        val period = 2 * numRow - 2

        val stringBuilder = StringBuilder(s.length)


        var p = period

        for (row in 0 until s.length) {

            var index = row

            p = numRow - 1

            while (index < s.length) {



                stringBuilder.append(s[index])


                index+ =

            }

        }

        return s
    }
}